package LeetCode刷题;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-10-08 15:47
 * @description: Functions of this class is
 * 最近公共祖先的情况无外乎三种情况，解答此题最好分别画出三种情况的草图，问题便迎刃而解
 * ○ 树形一：root为p,q中的一个，这时公共祖先为root
 * ○ 树形二：p,q分别在root的左右子树上（p在左子树，q在右子树；还是p在右子树，q在左子树的情况都统一放在一起考虑）这时满足p,q的最近公共祖先的结点也只有root本身
 * ○ 树形三：p和q同时在root的左子树；或者p,q同时在root的右子树，这时确定最近公共祖先需要遍历子树来进行递归求解。
 * 官方题解：
 *
 * }
 **/
public class NoNo二叉树的最近公共节点 {

    /**
     *     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
     *         if(root==null||root==p||root==q){//如果当前节点为空了、或者等于其中一个节点，则说明当前节点就为公共祖先了，直接返回
     *             return root;
     *         }
     *         TreeNode leftNode=lowestCommonAncestor(root.left,p,q);//向左树去递归
     *         TreeNode rightNode=lowestCommonAncestor(root.right,p,q);//向右树去递归
     *         if(leftNode==null){//如果一直向左遍历直到为空了都没有找到公共祖先,则返回右边的节点
     *             return rightNode;
     *         }
     *         if(rightNode==null){//如果一直向右遍历直到为空了都没有找到公共祖先,则返回左边的节点
     *             return leftNode;
     *         }
     *         return root;//都不为空的话就返回当前中间的节点为公共祖先
     *     }
     */

}